1. Field of the Invention
The present invention relates to a method and apparatus for decoding data stored on a mass storage medium, for example an optical storage disk that stores data in a DVD-ROM format.
2. Description of the Related Art
DVD-ROM (digital versatile disk, read only memory) is for many applications a successor product to the CD-ROM format popularly used for recording and distributing data. A single-side, single-layer DVD-ROM disk can hold up to 4.7 GB (gigabytes) of data, or about seven times the capacity of the conventional CD-ROM. The high storage capacity of DVD-ROM is achieved in part by recording data as smaller pits along narrower tracks, as compared to the way that data are stored on CD-ROM disks. DVD-ROM also achieves higher capacity as compared to CD-ROM by using a more efficient sector data encoding scheme. The data format and the data encoding scheme for DVD-ROM disks are considerably different and more complex than those used for CD-ROM disks. As such, data processing and error decoding functions are different for the newer DVD-ROM format.
Data processing and error decoding functions have been refined over the course of many years for CD-ROM devices. An example of the highly optimized data processing and decoding of CD-ROM data is illustrated in U.S. Pat. No. 6,003,151, which describes partially concurrent error detection and Reed-Solomon error correction for CD-ROM data. The techniques described in this patent provide incremental but significant improvements in data processing rates. Various other optimized data processing strategies are implemented to facilitate the high speed reading and processing of data from CD-ROM disks. Consequently, when DVD-ROM was initially introduced as a data storage medium, the highly refined CD-ROM processing and decoding techniques allowed CD-ROM devices to have significantly better data access times than the less refined and newer DVD-ROM devices. This initial performance disparity slowed the adoption of the DVD-ROM storage format. As such, there was and there continues to be a need to improve the processing and decoding of DVD-ROM data. Thus, while the error decoding schemes for DVD-ROMs are different and considerably more complex than those used for CD-ROM disks, aspects of the concurrent error detection and error correction schemes described in U.S. Pat. No. 6,003,151 conceivably might improve sector processing speed and capability for DVD-ROM drives.
Decoding DVD-ROM disks requires knowledge of the data encoding on the disk.
The DVD-ROM sector-encoding flow consequently is described to provide a background for understanding the improvements of the present invention. The encoding and decoding of CD-DA and CD-ROM data are described first for comparison purposes.
The original compact disk standard was promulgated and eventually adopted for the distribution of digitized audio. The resulting specification is called the Red Book (ICE 908) and the data storage medium was called CD-DA, for compact disk-digital audio. Two layers of error correction codes, identified as C1 and C2 in IEC 908 and ISO/IEC 10149, are encoded with the audio data on CD-DA. When such a disk is played back, the pits on the surface of the disk are sensed by a laser pickup head and converted to a serial bit stream. The bit stream is then demodulated and split to thirty-two byte frames that are processed by a C1 error corrector. The C1 error correction codes are (32, 28) Reed-Solomon codes over the Galois field GF(28) and can typically correct two errors in each frame. After the C1 corrections, the four C1 parity bytes are discarded, the other twenty-eight bytes in the frame are de-interleaved for the first time and the bytes are sent to the C2 error corrector. This first de-interleaving mixes data bytes from two adjacent C1-corrected frames to form the twenty-eight byte input to the C2 error corrector. The C2 error correction codes are (28, 24) Reed-Solomon codes over GF(28) and can typically correct two errors in each frame. After C2 error correction, the four C2 parity bytes are discarded and the remaining twenty-four bytes are de-interleaved for a second time. The second de-interleaving mixes data bytes from twenty-four different C2 frames to generate twenty-four bytes of audio data, organized as six couples of sixteen-bit left-channel and sixteen-bit right-channel digital audio data.
C1 and C2 error corrections reduce the error rates of the digital audio data read from a disk. Furthermore, the data bit exchange accomplished in the first and second de-interleaving processes improves the playability of defective disks. When a scratch on a disk surface introduces a burst of errors, the erroneous data are de-interleaved into many different frames, thus reducing the number of errors per frame and increasing the probability of successful error corrections. On the other hand, the inclusion of parity bytes for two layers of error correction codes greatly reduces the amount of data that can be stored on a disk.
When a compact disk is used as a digital data storage medium, generally the data are stored in the CD-ROM format, which adds a third layer of Reed-Solomon error correction codes to the CD-DA data formatting to ensure the integrity of data read from the CD-ROM disk. This third layer of error correction codes, sometimes called C3, is applied to 2352 byte frames (or sectors) extracted from the C1-and C2-corrected and twice de-interleaved data stream. Note that the 2352 byte frame is different from the thirty-two byte and twenty-eight byte frames to which the C1 and C2 layers of error correction codes are applied. In some documents, including ISO/IEC-10149, the C1 or C2 frame is called the small frame.
C3 is a Reed-Solomon product-like code (RSPC), as is described in ISO/IEC-10149 and in U.S. Pat. No. 6,003,151. A thirty-two bit error detection code (EDC) is also encoded in CD-ROM sectors to provide a further data integrity check, generally in the form of a cyclic redundancy code. The utilization of C3 and EDC encoding further limits the capacity of digital data that can be stored on a CD-ROM. As a matter of fact, to record 2048 bytes (16384 bits) of user data according to the CD-ROM format, 57624 channel bits are stored on the surface of a CD-ROM.
DVD-ROM is a general-purpose data storage medium. Unlike the CD-ROM format, which may store data in a variety of sector formats, e.g., Mode 1 and Mode 2 Form 1, the DVD-ROM format stores data in only one sector format. Each DVD-ROM data sector consists of 2048 bytes of main data (similar to the user data in a CD-ROM sector), twelve bytes of identification data (ID) and other header data, and four bytes of error detection code data (EDC). FIG. 1 shows the data sector configuration for a DVD-ROM disk.
The four-byte identification data (ID) contains attributes and the physical address of the DVD-ROM sector. The bits of the identification data and the ID error detection code (IED) together form a (6, 4) Reed-Solomon code, which is decoded to detect as well as to correct errors in the important ID data. The six-byte copyright management information (CPR-MAI) provides data for copyright protection and region management. The error detection code (EDC) is a four-byte cyclic redundancy check code attached to the 2060 bytes of ID, IED, CPR_MAI and main data before scrambling. Calculation of the EDC for each 2060 byte codeword is conventional and can be illustrated as follows. Suppose the MSB of the first byte of ID is b16511 and the LSB of the last byte of the EDC is b0, then the EDC code word is selected so that the polynomial
I(x)=b16511x16511+ . . . +b2x2+b1x+b0xe2x80x83xe2x80x83(1)
is evenly divisible by the polynomial g(x)=x32+x31+x4+1. The four-bytes of EDC data are determined separately for each EDC codeword to cause the polynomial assembled according to Equation 1 to be evenly divisible by this check polynomial g(x). Note that the check polynomial g(x) for the DVD-ROM format is different from the EDC check polynomial dictated by the CD-ROM standard.
After EDC calculation, the main data are scrambled by exclusive-ORing the main data with a string of bytes selected according to the sector identity or position within a block or sector. Sixteen different addresses are assigned among sixteen main data sectors and each of the sixteen sectors is scrambled with a predetermined string of scrambling bytes. Sixteen different scrambling strings are used corresponding to the sixteen different addresses. The sixteen scrambled data sectors are then grouped into an ECC block, which is encoded using a Reed-Solomon product code. FIG. 2 shows the ECC block configuration.
To construct an ECC block, sixteen scrambled data sectors, each 172 bytes by twelve rows, are concatenated to form a 172-byte by 192-row matrix, as shown in the upper-left portion of FIG. 2. Ten inner-code parity (PI) bytes are appended to each of the 192 rows of Main Data to produce a (182, 172) Reed-Solomon code. Finally, sixteen outer-code parity (PO) bytes are appended to each of the 182 columns to produce a (208, 192) Reed-Solomon code. The resulting ECC block is a 208-row by 182-byte matrix, where the rows are (182, 172) Reed-Solomon codes called the inner codes, and the columns are (208, 192) Reed-Solomon codes called the outer codes.
When an ECC block like that illustrated in FIG. 2 is recorded on a disk, the sixteen rows of outer-code parity bytes PO are interleaved to the end of each of the twelve rows of sector data and inner-code parity, as shown in FIG. 3. The data consisting of thirteen rows of 182 bytes forming the ECC block after row interleave are collectively referred to as the recording sector. Recording sectors are finally converted by {fraction (8/16)} modulation and SYNC-code insertion to provide a sequence of channel bits, which becomes the reflectivity modulation on the surface of the DVD-ROM disk.
Table I provides a comparison between aspects of the data formatting, processing and error protection for CD-ROM and DVD-ROM disk formats.
An aspect of the present invention provides a method of correcting and detecting errors in data within a device adapted for the retrieval and processing of data stored on an optical disk in a DVD format, where the retrieval and processing of data includes inner and outer code error correction for a Reed-Solomon product like code and an error detection process for evaluating an extent of errors in a sector of data. For this device, the sector of data is encoded within a plurality of inner codes and parts of plural sectors encoded within each outer code. The method includes passing the sector through a CRC generator to generate an initial error detection value for the sector and comparing the initial error detection value to a target error detection value to determine if errors are present in the sector. Responsive to the process of comparing the initial error detection value to the target error detection value, the method determines whether or not one or more error correction operations are to be performed on data wholly or partially within the sector. Subsequently the data within the sector are descrambled and output.
An aspect of the present invention provides a method of correcting and detecting errors in data within a device adapted for the retrieval and processing of data stored on an optical disk in a DVD format, where the retrieval and processing of data includes inner and outer code error correction for a Reed-Solomon product like code and an error detection process for evaluating an extent of errors in a sector of data. For this device, the sector of data is encoded within a plurality of inner codes and parts of plural sectors encoded within each outer code. The method includes calculating an initial error detection value for data within the sector, the data within the sector scrambled so as to be descrambled before use by a host. An error correction operation is performed on the data within the sector and an updated, intermediate error detection value responsive to the error correction operation is determined. The intermediate error detection value is compared to a target error detection value to determine if errors are present in the sector, the target error detection value representative of information used in scrambling the data within the sector. Responsive to the process of comparing the intermediate error detection value to the target error detection value, the method determines whether or not one or more error correction operations are to be performed on data wholly or partially within the sector.
An aspect of the present invention provides a method of correcting and detecting errors in data within a device adapted for the retrieval and processing of data stored on an optical disk in a DVD format, where the retrieval and processing of data includes inner and outer code error correction for a Reed-Solomon product like code and an error detection process for evaluating an extent of errors in a sector of data. For this device, the sector of data is encoded within a plurality of inner codes and parts of plural sectors encoded within each outer code. The method includes calculating an initial error detection value for data within the sector and performing an error correction operation on the data within the sector and determining an updated, intermediate error detection value responsive to the error correction operation. The method compares the initial or intermediate error detection value to a target error detection value to determine if errors are present in the sector. Responsive to the process of comparing the initial or intermediate error detection value to the target error detection value, the method determines that the sector does not include errors and then processes an outer code to provide a set of error patterns and error locations. If any of the error locations are for data within the sector and data corresponding to the error locations within the sector is not corrected.